from math import fabs
import copy
import operator

#__all__ = ['is_equal', 'is_sub']

OBJECT_TYPES = (dict,)
ARRAY_TYPES = (list, tuple)
FLOAT_TYPES = (float, complex)

def is_fpequal(left, right, ftol=1e-10):
    '''Return True if two JSON-like structures are equivalent'''

    return not any(iterdiff(left, right, ftol))


def iterdiff(left, right, root=None, eq_op=operator.eq):
    '''
    Return the differences from going from left to right.
    
    @param left:
    @param right:
    @param root:
    @param eq_op:
    '''
    root = (root if root else [])

    # Compare Object types
    if isinstance(left, OBJECT_TYPES):
        for key, lvalue in left.items():
            try:
                rvalue = right[key]
            except KeyError:
                yield ('-', root + [key])
            else:
                for dobj in iterdiff(lvalue, rvalue, root + [key], eq_op):
                    yield dobj

        for key, value in right.items():
            if key not in left:
                yield ('+', root + [key], value)

    # Compare Arrays
    elif isinstance(left, ARRAY_TYPES):
        for idx, (lvalue, rvalue) in enumerate(zip(left, right)):
            for dobj in iterdiff(lvalue, rvalue, root + [idx], eq_op):
                yield dobj

        larger = max(left, right)
        smaller = (right if left is larger else left)
        n_small = len(smaller)
        iterator = enumerate(larger[n_small:])
        if left is larger:
            iterator = reversed(list(iterator))
        for idx, value in iterator:
            idx += n_small
            if larger is left:
                yield ('-', root + [idx])
            else:
                yield ('+', root + [idx], value)

    # Compare Floats
    elif not eq_op(left, right):
        yield ('=', root, right)

def diff_apply(diff, obj, inplace=False):
    if not inplace:
        obj = copy.deepcopy(obj)

    ops = {'+': op_add, '-': op_rem, '=': op_add}
    for cmd in diff:
        ops[cmd[0]](obj, *cmd[1:])
    return obj

def op_add(obj, path, value):
    key = path[-1]
    for dir in path[:-1]:
        obj = obj[dir]
    else:
        if isinstance(obj, ARRAY_TYPES):
            if len(obj) == key:
                obj.append(value)
            else:
                obj[key] = value
        else:
            obj[key] = value

def op_rem(obj, path):
    key = path[-1]
    for dir in path[:-1]:
        obj = obj[dir]
    else:
        if isinstance(obj, ARRAY_TYPES):
            N = len(obj)
            while key <= N:
                obj.pop()
        else:
            try:
                del obj[key]
            except KeyError:
                pass

def is_sub(obj, super):
    '''
    Check if 'obj' is a subset of 'super'. The super must have all keys in 
    obj and may have additional keys. 
    '''
    # Compare Object types
    if isinstance(obj, OBJECT_TYPES):
        for key, value in obj.items():
            try:
                if not is_sub(value, super[key]):
                    return False
            except KeyError:
                return False
        return True

    # Compare Arrays
    elif isinstance(obj, ARRAY_TYPES):
        idx = 0
        for left, right in zip(obj, super):
            idx += 1
            if left != right:
                return False
        return idx == len(obj)

    # Compare simple object types
    else:
        return obj == super

if __name__ == '__main__':
    d1 = {'foo': 'bar', 'ham': 'spam', 'inner': [1, 2, 3]}
    d2 = {'bacon': 'eggs', 'ham': 'spam', 'inner': [3, 2, 1, 0, -1]}
    df = list(iterdiff(d1, d2))
    print df
    print d1
    print d2
    print diff_apply(df, d1)

    order1 = {'food': {'ham': 2, 'eggs': 1}, 'drinks': ['juice']}
    order2 = {'food': {'ham': 2, 'eggs': 1, 'bacon': 1}, 'drinks': ['juice', 'milk']}
    print(is_sub(order1, order2))
    print(is_sub(order2, order1))
